package org.example.myleet.p684;

public class Solution {
    /**
     * 1 ms
     * 使用并查集检查是否存在相同的根节点
     */
    public int[] findRedundantConnection(int[][] edges) {
        int N = 0;
        for (int[] edge : edges) {
            N = Math.max(N, edge[0]);
            N = Math.max(N, edge[1]);
        }
        UnionFind uf = new UnionFind(N+1);
        for (int[] edge : edges) {
            if (uf.find(edge[0]) == uf.find(edge[1])) {
                //如果一条边的两个节点存在相同的根节点，说明这条边是冗余的
                return edge;
            }
            uf.union(edge[0], edge[1]);
        }
        return edges[edges.length-1];
    }

    static class UnionFind {
        int[] parent;

        int[] height;

        public UnionFind(int len) {
            parent = new int[len];
            for (int i=0;i<len;i++) {
                parent[i] = i;
            }
            height = new int[len];
        }

        public int find(int x) {
            int p = parent[x];
            while (p != parent[p]) {
                p = parent[p];
            }
            return p;
        }

        public void union(int x, int y) {
            //路径压缩的并查集
            int rootX = find(x);
            int rootY = find(y);
            if (height[x] == height[y]) {
                parent[rootY] = rootX;
                height[rootX]++;
            } else if (height[x] < height[y]) {
                parent[rootX] = rootY;
            } else {
                parent[rootY] = rootX;
            }
        }
    }
}
